//
// Created by haozhenghui on 2020/12/1.
//

#include "sort/sort.h"
#include <string.h>
#include <stdlib.h>
#include <stdio.h>

static int compare_int(const void *int1, const void *int2) {
    if (*(const int *) int1 > *(const int *) int2) {
        return 1;
    } else if (*(const int *) int1 < *(const int *) int2) {
        return -1;
    } else {
        return 0;
    }
}

static int partition(void *data, int esize, int i, int k, int (*compare)(const void *key1, const void *key2)) {
    char *a = data;
    void *pval = NULL, *temp = NULL;
    int randArray[10] = {0};
    if ((pval = malloc(esize)) == NULL) {
        return -1;
    }
    if ((temp = malloc(esize)) == NULL) {
        free(pval);
        return -1;
    }

    randArray[0] = (rand() % (k - i + 1)) + i;
    randArray[1] = (rand() % (k - i + 1)) + i;
    randArray[2] = (rand() % (k - i + 1)) + i;
    issort(randArray, 3, sizeof(int), compare_int);
    memcpy(pval, &a[randArray[1] * esize], esize);
    printf("pval:%d\n", *(char *) pval);
    i--;
    k++;
    while (1) {
        do {
            k--;
        } while (compare(&a[k * esize], pval) > 0);
        do {
            i++;
        } while (compare(&a[i * esize], pval) < 0);
        if (i >= k) {
            break;
        } else {
            printf("a:%d\n", a[i * esize]);
            printf("i:%d,k:%d\n", i, k);
            memcpy(temp, &a[i * esize], esize);
            memcpy(&a[i * esize], &a[k * esize], esize);
            memcpy(&a[k * esize], temp, esize);
        }
    }
    if (temp != NULL) {
        free(temp);
    }
    if (pval != NULL) {
        free(pval);
    }
    printf("k:%d\n", k);
    return k;
}

int qksort(void *data, int size, int esize, int i, int k, int (*compare)(const void *key1, const void *key2)) {
    int j = 0;
    while (i < k) {
        j = partition(data, esize, i, k, compare);
        if (j < 0) {
            return -1;
        }
        if (qksort(data, size, esize, i, j, compare) < 0) {
            return -1;
        }
        i = j + 1;
    }
    return 0;
}

